GATE CSE 2016 SET-1
Q41.
Let a_{n} be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for a_{n}?Q42.
Consider the recurrence relation a_{1}=8, a_{n}=6n^{2}+2n+a_{n-1}. Let a_{99}= K \times 10^{4}. The value of K is .Q43.
Let p,q, r, s represent the following propositions. p: x\in{8,9,10,11,12} q: x is a composite number r: x is a perfect square s: x is a prime number The integer x\geq2 which satisfies \neg((p\Rightarrow q)\wedge (\neg r \vee \neg s)) is ________.Q44.
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?Q45.
Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below. The maximum possible number of iterations of the while loop in the algorithm is_________.Q46.
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that \bar{Y} reduces to W, and Z reduces to \bar{X} (reduction means the standard many-one-reduction). Which one of the following statements is TRUE?Q47.
Which of the following is NOT a superkey in a relational schema with attributes V,W, X, Y, Z and primary key V Y?Q48.
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?Q49.
A function f:\mathbb{N}^{+}\rightarrow \mathbb{N}^{+}, defined on the set of positive integers \mathbb{N}^{+}, satisfies the following properties: f(n)=f(n/2) if n is even f(n)=f(n+5) if n is odd Let R={i|\exists j:f(j)=i} be the set of distinct values that f takes. The maximum possible size of R is ____.Q50.
The worst case running times of Insertion sort, Mergesort and Quicksort, respectively, are: